package com.lh.nk;

import java.util.*;

/**
 * @author: linghao
 * @since: 2023/2/4
 *
 * 描述
 * 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
 * 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
 */
public class 最长无重复子数组NC41 {

    //双指针，hash，类似题目 两数之和NC61
    public int maxLength (int[] arr) {
        // write code here
        Map<Integer,Integer> aMap = new HashMap<>();
        int max = 0;
        for(int i=0,j=0;i<arr.length;i++){
            if(aMap.containsKey(arr[i])){
                j = Math.max(j,aMap.get(arr[i])+1);
            }
            aMap.put(arr[i],i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }

    //利用队列
    public int maxLength2 (int[] arr) {
        // write code here
        int max = 0;
        Queue<Integer> linkedList = new LinkedList<>();
        for(int i : arr){
            while (linkedList.contains(i)){  //这里一定要用while
                linkedList.poll();
            }
            linkedList.add(i);
            max = Math.max(max,linkedList.size());
        }
        return max;
    }
}
